#include<iostream>
#include<vector>
#include<math.h>
#include<cstdlib>
#include<ctime>
//#include<RandomNumber.h> 
using namespace std;
class RandomNumber
{
	public:
		RandomNumber(){
			srand(time(0));
		}
		unsigned random(int,int);
	private:
		
};
unsigned RandomNumber::random(int begin=0,int end=1)
{
	return rand()%(end-begin+1)+begin; 
}

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        if(nums.empty()) return 0;
        int result = INT_MIN;
        int numsSize = nums.size();
        result = maxSub(nums, 0, numsSize - 1);
        return result;
    }

    int maxSub(vector<int> &nums, int left, int right)
    {
        if (left == right)
        { 
            return nums[left];
        }
        int mid = (left + right) / 2;
        int leftSum = maxSub(nums, left, mid);              //计算左边最大子段
        int rightSum = maxSub(nums, mid + 1, right);          //计算右边最大子段
        int midSum = maxMidSub(nums, left, mid, right);
        int result = max(leftSum, rightSum);
        result = max(result, midSum);
        return result;
    }	

    int maxMidSub(vector<int> &nums, int left, int mid, int right) //计算中间最大子段
    {
        int leftSum = INT_MIN;
        int sum = 0;
        for (int i = mid; i >= left; i--)
        {
            sum += nums[i];
            leftSum = max(leftSum, sum);
        }

        int rightSum = INT_MIN;
        sum = 0;
        for (int i = mid + 1; i <= right; i++)
        {
            sum += nums[i];
            rightSum = max(rightSum, sum);
        }
        return (leftSum + rightSum);
    }
};
int main()
{
	
	int b[]={1,2,3,1,2,3};    //情况一:输入的元素全部为正整数 
	vector<int> a(b,b + 6); 
/*	int b[]={-1,-2,-3,-1,-2,-3};    //情况二:输入的元素全部为负整数
	vector<int> a(b,b + 6); */
/*	int b[]={-1,2,3,1,-2,-3};    //情况三:输入的元素包含正整数与负整数
	vector<int> a(b,b + 6); */
/*	int b[]={};    //情况四:输入的数据为空
	vector<int> a(b,b + 0); */
/*	vector<int> a;				//	情况五:输入的数据量极大
	
	for(int i = 0;i < 1000000;i++)
	{
		a.push_back(i);
	} */ 
/*	vector<int> a;				// 情况六:随机数
	RandomNumber number;
	for(int i = 0;i < 10000;i++)
	{	
		int b;
		b = number.random(-1000,1000);
	//	cout<<b<<" ";
		a.push_back(b);
	}
	cout<<endl;
*/ 

	Solution c;
	int d;
	d = c.maxSubArray(a);
	cout<<d<<endl;
	
	return 0;	
} 
